Software defined networking (SDN) is an approach to networking that enables applications to communicate with and manipulate the control software of network devices and resources. A key aspect of SDN is the abstraction between the forwarding and the control/management planes in order to separate them and provide applications with the means necessary to control the network. This separation provides faster innovation cycles at both planes.
In SDN, the control plane and the forwarding plane communicate via a southbound interface using protocols such as Forwarding and Control Element Separation (ForCES), Network Configuration Protocol (NETCONF), and Interface to the Routing System (I2RS). Through the southbound interface, the control plane manages the forwarding plane behavior by manipulating the corresponding forwarding tables.
A conventional forwarding plane includes a pipeline of functional blocks to handle packets from ingress to egress. The corresponding forwarding tables attached to the functional blocks include ingress/egress Access Control List (ACL), Forwarding Information Base (FIB), Label FIB (LFIB), etc.
The FIBs are typically implemented in Static Random Access Memory (SRAM) or Dynamic Random Access Memory (DRAM) as trie-trees (also commonly known as radix trees). ACL tables are also typically implemented as multiple combined trie-tree based algorithms (e.g., hierarchical trie, set-pruning trie, etc.) A typical trie tree includes multiple levels of nodes. The number of levels of nodes defines the depth of the trie tree, which defines the number of steps for the trie tree to complete a search. The depth of a trie tree depends on its strides planning. As used herein, a “stride” refers to the amount of information (e.g., the number of bits) that are compared/searched during each step (i.e., at each level of the trie tree). Thus, larger strides results in smaller depths.
The FIBs can be implemented as hash tables, which may employ different hashing functions. Some hash tables may result in collisions. As used herein, a “hashing collision” refers to the phenomenon where an input maps to multiple outputs. Thus, hashing may involve two steps. The first step is to find the result. In some instances, hashing requires a second step to be performed, i.e., collision resolution. Different collision resolution algorithms may be utilized by a hash table. Further, each hash table is associated with a load factor. As used herein, a “load factor” refers to the number of hash entries divided by the number of buckets. If the load factor is kept reasonable, the hash table should perform well, provided the hashing is good. If the load factor grows too large, the hash table will become slow, or it may fail to work altogether. Thus, the performance of hashing tables depends on the hashing function, the collision resolution algorithm, the load factor, or any combination thereof.
When the forwarding plane includes multiple forwarding tables, the overall performance of the forwarding tables depends on the performance of all forwarding tables in the pipeline. If one forwarding table becomes the bottleneck, then the entire pipeline of forwarding tables is impacted. In some networking applications, control of the performance of the forwarding tables is required. Conventionally, there is no mechanism for controlling the performance of these forwarding tables.
Further, in some network configurations, multiple virtual routers are executed by the same processor, sharing the same hardware resource (e.g., memory) for implementing the forwarding tables to satisfy different Service Level Agreements (SLAs). In such configurations, forwarding tables with higher priorities may over utilize the hardware resources and starve the lower priority forwarding tables. Conventionally, there is no mechanism for controlling the resource consumption by the forwarding tables.